package 滑动窗口;

import java.util.HashMap;
import java.util.Map;

public class No567字符串的排列 {

    /**
     * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
     * 换句话说，第一个字符串的排列之一是第二个字符串的子串。
     * 示例1:
     * 输入: s1 = "ab" s2 = "eidbaooo"
     * 输出: True
     * 解释: s2 包含 s1 的排列之一 ("ba").

     找到一套解题模板,虽然里面有两个while,但是其实和我的一个while里面加if else是一样的,它将else的情况
     放到里while里面了,在第一个while里面进行移动右指针,然后进入第二个while是有条件的,条件就是是否满足条件
     去移动左指针。
    */


    /**
     * 总结:双map用法,只看自己需要的字符
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkInclusion(String s1, String s2) {
        int left=0;
        int right=0;
        //合格数,当合格数与need的size相等,则表明need已吃满,return true
        int valid=0;
        Map<Character,Integer> need=new HashMap<>();
        Map<Character,Integer> window=new HashMap<>();
        for(int i=0;i<s1.length();i++){
            //有则取出,没有就用默认的值
            need.put(s1.charAt(i),need.getOrDefault(s1.charAt(i),0)+1);
        }

        while(left<s2.length()){

            /**
             * 1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
             * 更新map的value减1(好像不用关心什么时候右指针移动?)
             * 2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
             * 当右指针-左指针的值大于等于s1时
             * 3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
             * 让map对应的value++
             * 4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
             * 在放大时更新(因为缩小时不会只会少,不会正好)
             */
            if(right<s2.length()&&need.containsKey(s2.charAt(right))){
                //吃入window
                char c=s2.charAt(right);
                window.put(c,window.getOrDefault(c,0)+1);
                //还需要维护什么呢?valid
                if(window.get(c).equals(need.get(c)))
                    valid++;
            }
            right++;

            //比较一下
            if(valid==need.size())
                return true;

            //移动左指针,因为right会一直++,如果right已经出界了,这里只是移动一次但是因为外面是while所以不怕

            if(right-left>=s1.length()){
                char c=s2.charAt(left);
                if(need.containsKey(c)) {
                    if (window.get(c).equals(need.get(c))) {
                        valid--;//下面会减少,所以这里提前维护
                    }
                    window.put(c,window.get(c)-1);
                }
                //吐出window
                left++;
            }

        }
        return false;
    }

    public static boolean checkInclusion2(String s1, String s2) {
        //比较目标
        HashMap<Character,Integer> need = new HashMap<>();
        //窗口内的值
        HashMap<Character,Integer> window = new HashMap<>();

        char[] c1 = s1.toCharArray();

        char[] c2 = s2.toCharArray();
        //填入比较Map
        for (int i = 0; i < c1.length; i++) {
            need.put(c1[i],need.getOrDefault(c1[i],0) + 1);
        }
        //[left,right]
        int left = 0;
        int right = 0;
        //合格的字符数
        int valid =0;
        //比较条件
        while(right < c2.length){

            /**
             * 这里解题之所以能成功,和我的那个差异是因为这里使用了两个map,
             * 即使是多的也不怕,只需要比较两个map即可
             */

            char c = c2[right];
            //一直可以右移动
            right++;
            //needMap存在就进入
            if(need.containsKey(c)){
                //添加进窗口map
                window.put(c,window.getOrDefault(c,0) + 1);
                //如果needMap和窗口map的value相同,则表明一个字符已经完成,则合格++
                if (need.get(c).equals(window.get(c))){
                    valid++;
                }
            }

            System.out.println("["+left+"  " + right +"]");

            //左指针移动条件   这里可以把-1去掉,换成等于可以吗?
            while(right - left  >= c1.length){
                //如果合格数与需要字符数相同就true
                if (valid == need.size()){
                    return true;
                }
                //不然开始移动左指针,移动左指针是为了什么呢?一次只会吐出一个!所以这个while比较牵强,不过模板还行
                //移动了一次左指针,那么下次就要开始移动右指针了
                char d = c2[left];
                left++;
                if (need.containsKey(d)){
                    //减少合格数,因为这里已经被吐出去了,必定会少
                    if (need.get(d).equals(window.get(d))){
                        valid--;
                    }
                    //窗口map也吐出
                    window.put(d,window.getOrDefault(d,0) - 1);
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        boolean b = checkInclusion("hello", "ooolleoooleh");
        System.out.println(b);
    }

}
